The present invention relates generally to dynamic networks of communications and computational resources, and more particularly, to methods that provide precedence adjusted resource allocation in such dynamic networks.
There is a different community of prior art related to each of these networks, communications managers and computational resource managers. The present invention is unique in both of these application communities.
Communication network and computational system performance can be dynamic for two reasons: topology changes and congestion/contention. The topology changes due to failure/creation of links or failure/creation of nodes. A link may be destroyed because of fade due to distance change or media becoming more opaque; a computational node may find that its battery is running dangerously low and removes itself from the network. Both of these affect the topology of the network that can in turn affect the network's performance. The other cause of performance degradation is congestion. Here, throughput for a particular communication stream or computational application can be temporarily decreased by demands from other sources. Whether dynamic changes are due to topology or to congestion, the network cannot guarantee continuous, full throughput to all users. Not everyone will be able to get complete satisfaction, who does? And how does the system determine who does get complete, partial, or minimal service?
Prior art of the communications community, when bandwidth gets temporarily decreased on a link or through a node, will completely drop some connections, forcing them to switch to a backup path, and if one had not been set up, the connection will be completely interrupted until a new path was found. Although methods of the prior art can usually discover alternate paths through the network to route around link faults, users will still experience abrupt disconnects lasting for varying lengths of time. In addition, the decision mechanisms that controls who will get the congested resources are either very expensive (i.e., require a lot of bandwidth and computation) or provide unpredictable overall network performance. This problem is especially serious for high priority applications such as military battlefield communications or emergency networks in disaster areas where there are some applications that require particular support.
Prior art of the computation community that addresses this situation relate to “active networks” research efforts. These use communication protocols to load balance the network of communication and computational resources by factoring in computational costs at the nodes into the communication link cost formulas used by the routing protocol; for instance, the Open Shortest Path First (OSPF) protocol uses a sum of link costs to determine shortest paths and now the computational node costs would be added in. (See Ralph Keller, et al., “Active Pipes: Service Composition for Programmable Networks”, Proceedings 2001 Milcom) Though this approach provides much more flexibility than the standard load sharing techniques, because it relies on the communication protocols, it suffers the faults those have, in particular non-graceful degradation of service and no prioritization of service.
There is an additional community somewhat between these two, referred to as the multimedia delivery community. They have prior art that uses a layered approach for communications in combination, with a computational approach for reconstructing the original streams. (See Lidia Yamamoto and Guy Leduc, “An Active Layered Multicast Adaptation Protocol” Second International Working Conference on Active Networks (1WAN 2000), Tokyo Japan, October 2000) For instance, the Active Layered Multicast Adaptation Protocol (ALMA) splits a multimedia stream into a hierarchy of flows so that “best possible” multicast can be achieved. In this method, a multicast application is a single source and multiple receivers and produces hierarchically layered traffic. Each layer is packetized separately into capsules that also contain instructions as to how to process it an intermediate active nodes. These nodes compare the cost of the outbound link with the budget the capsule carries to determine whether to transmit the capsule or discard it. The hierarchical layering is such that the lower layers stand by themselves but higher layers need the lower layers. Thus, lower layer capsules have a higher budget and tend to make it through, whereas the higher level is most prone to discard if there is congestion.
This methodology clearly has the advantage that there is graceful degradation of service as opposed to the all-or-nothing service of the other two prior art areas. However, this community is focused pretty narrowly on the multicast delivery of multimedia services and thus issues of managing the multicast tree are prominent in their literature. They are not looking at the management of mixed traffic networks where there is connectionless and connection oriented. Also, the management functions are initiated at the edges (the source or the receiver) and thus cannot be responsive to local contexts.
It is therefore an objective of the present invention to provide for methods that provide for precedence adjusted resource allocation in dynamic networks that provide optimal service with respect to local contexts for the most necessary traffic while still providing as good as possible for the other traffic.